package com.xzz.dp;

import java.util.Arrays;

/**
 * @author: hhz
 * @create: 2022-01-17 09:26
 * 1220. 统计元音字母序列的数目
 **/
public class CountVowelPermutation {
    public static void main(String[] args) {
        System.out.println(countVowelPermutation(1));
        System.out.println(countVowelPermutation(2));
        System.out.println(countVowelPermutation(3));
        System.out.println(countVowelPermutation(144));
    }
    public static int countVowelPermutation(int n) {
        int MOD = (int)1e9+7;
        //定义dp[i][j]表示i+1长度的字符串以j为结尾（j为[a,e,i,o,u]的下标）的方案数
        long[][] dp = new long[n][5];
        Arrays.fill(dp[0], 1);
        for (int i = 1; i <n; i++) {
            //以a结尾
            dp[i][0]= dp[i-1][1]+dp[i-1][2]+dp[i-1][4];
            //以e结尾
            dp[i][1]= dp[i-1][0]+dp[i-1][2];
            //以i结尾
            dp[i][2]= dp[i-1][1]+dp[i-1][3];
            //以o结尾
            dp[i][3]= dp[i-1][2];
            //以u结尾
            dp[i][4]= dp[i-1][2]+ dp[i-1][3];
            for (int j = 0; j < 5; j++) {
                dp[i][j] %= MOD;
            }
        }

        long sum = 0;
        for (int i = 0; i <= 4; i++) {
            sum+=dp[n-1][i];
        }
        return (int)(sum % MOD);
    }
}
